//https://leetcode.cn/problems/two-sum/
class Solution1 {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            if(hash.count(target - nums[i])) return {hash[target - nums[i]], i};
            hash[nums[i]] = i;
        }
        return {};
    }
};


//https://leetcode.cn/problems/check-permutation-lcci/
class Solution2 {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        int count = s1.size();
        if(count != s2.size()) return false;
        int hash[26] = {0};
        for(auto& c: s1)
        {
            hash[c - 'a']++;
        }
        for(auto& c: s2)
        {
            if(hash[c - 'a']--) count--;
        }
        return count==0? true:false;
    }
};

//https://leetcode.cn/problems/contains-duplicate/
class Solution3 {
public:
    bool containsDuplicate(vector<int>& nums) //map解决
    {
        unordered_map<int, int> hash;
        for(auto& a: nums)
        {
            if(hash.count(a)) return true;
            hash[a]++;
        }
        return false;
    }
};


class Solution3_1 {
public:
    bool containsDuplicate(vector<int>& nums) //set解决
    {
        unordered_set<int> hash;
        for(auto& a: nums)
        {
            if(hash.count(a)) return true;
            hash.insert(a);
        }
        return false;
    }
};


//https://leetcode.cn/problems/contains-duplicate-ii/
class Solution4 {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) //
    {
        unordered_map<int ,int> hash;
        for(int i = 0; i < nums.size(); i++)
        {
            if(hash.count(nums[i])) 
            {
                if(i - hash[nums[i]] <= k) return true;
            }
            hash[nums[i]] = i; 
        }
        return false;
    }
};


//https://leetcode.cn/problems/group-anagrams/
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) //泛型编程的强大
    {
        vector<vector<string>> vvs;
        unordered_map<string, vector<string>> hash;
        for(int i = 0; i < strs.size(); i++)
        {
            string str = strs[i];
            sort(str.begin(), str.end());//先将其排序
            hash[str].push_back(strs[i]);
        }
        for(auto vs:hash)
        {
            vvs.emplace_back(vs.second);
        }
        return vvs;
    }
};